import org.junit.jupiter.api.Test;

public class Demo {
    //算法的时间复杂度分析
    //随着输入规模的增大，算法的常数操作可以忽略不计
    //随着输入规模的增大，与最高次项相乘的常数可以忽略
    //最高次项的指数大的，随着n的增长，结果也会变得增长特别快
    //在我们比较算法随着输入规模的增长量时，可以有以下规则：
    //1.算法函数中的常数可以忽略；
    //2.算法函数中最高次幂的常数因子可以忽略；
    //3.算法函数中最高次幂越小，算法效率越高。
    //线性阶O(n) 平方阶O(n^2) 立方阶O(n^3) 对数阶O(logn)  常数阶O(1)
    //效率高到底 O(1) >O(logn) >O(n)>O(nlogn)>O(n^2)>(n^3)


    @Test
    //最坏情况
    // 假如有一个需求：
    //有一个存储了n个随机数字的数组，请从中查找出指定的数字。
    public int test10(){
        int num=0;
        int[] arr={11,10,8,9,7,22,23,0};
        for (int i=0;i<arr.length;i++){
            if (num==arr[i]){
                return i;
            }
        }
        return -1;
    }
    //最好情况：
    //查找的第一个数字就是期望的数字，那么算法的时间复杂度为O(1)
    //最坏情况：
    //查找的最后一个数字，才是期望的数字，那么算法的时间复杂度为O(n)
    //平均情况：
    //任何数字查找的平均成本是O(n/2)


    //分析函数调用过程中时间复杂度
    @Test
    // O(n)
    public void test07() {
        int n = 100;//执行1次
        for (int i = 0; i < 100; i++) {
            show07(i);//执行n次
        }
    }

    public void show07(int i) {
        System.out.println(i);
    }

    @Test
    //O(n^2)
    public void test08() {
        int n = 100;//执行1次
        for (int i = 0; i < 100; i++) {
            show08(i);//执行n次
        }
    }

    public void show08(int i){
        for (int j=0;j<i;j++){
            System.out.println(i);//执行n^2次
        }
    }

    @Test
    //O(n^2)
    public void test09(){
        int n=100;
        show09(n);//执行n次
        for(int i=0;i<n;i++){
            show09(i);//执行n^2次
        }
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                System.out.println(j);//执行n^2次
            }
        }
    }

    public void show09(int i){
        for (int j=0;j<i;j++){
            System.out.println(i);
        }
    }
    @Test
    //常数阶O(1)
    public void test06() {
        int n = 0;
        int i = n + 2;
    }

    @Test
    //计算1000个1+1000个2....加到1000  大O记法O(N^3)
    public void test05() {
        long num = 0;
        int x = 0, n = 1000;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                for (int z = 1; z <= n; z++) {
                    num += i;
                    x++;
                }
            }
        }
        System.out.println(num);
        System.out.println(x);
    }

    @Test
    //计算100个1+100个2....加到100  大O记法O(N^2)
    public void test04() {
        int n = 100;
        int num = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                num += i;//执行n的平方次
            }
        }
        System.out.println(num);
    }

    @Test
    //计算1加到100 大O记法O(N)
    public void test02() {
        int sun = 0;//执行一次
        int n = 100;//执行一次
        for (int i = 0; i <= 100; i++) {//执行n+1次
            sun += i;//执行n次
        }
        System.out.println(sun);
    }

    @Test //大O记法O(1)
    public void test03() {
        int sun = 0;//执行一次
        int n = 100;//执行一次
        sun = (n + 1) * n / 2;//执行一次
        System.out.println(sun);
    }


    @Test
    //计算n的乘阶
    public void test01() {
        long result = method01(10);
        System.out.println("方法01=" + result);
        long result02 = method02(10);
        System.out.println("方法02=" + result02);
    }

    //方法1 递归调用 调用10次 大O记法O(1)
    public long method01(long n) {//执行10次
        if (n == 1) {
            return 1;
        }
        return n * method01(n - 1);
    }

    //方法2 调用1次 大O记法O(n)
    public long method02(long n) {//执行一次
        int result02 = 1;//执行一次
        for (long i = 1; i <= n; i++) {//执行n次
            result02 *= i;
        }
        return result02;
    }
}
